package com.wzh.test;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个表达时1 + (6+2) * 3
 * 求值是多少
 * <p>
 * 转为中间态 去掉括号 把运算符放到数字后面 ： 1 6 2 + 3 * +
 * 1 + (6+2) * 3 这种形态，运算符在中间，称为中缀表达式
 * 1 6 2 + 3 * + 这种形态，去掉了括号，运算符在后面，称为后缀表达式
 * 如何转换呢？
 * 1、所有的数字直接输出
 * 2、运算符优先级高于栈内的要入栈（或栈空）。否则，从栈中弹出所有优先级更高或一样的运算符（或直到括号），再将当前的入栈。
 * 3、所有左括号都要入栈
 * 4、若栈内包含左括号，运算符都要入栈
 * 5、若是右括号，栈内不断出栈，知道碰到左括号
 */
public class StackDemo {
    public static void main(String[] args) {
        String expression = "1+(6+2)*3*2+1*8+5";
        Set<String> ops = new HashSet<>();
        ops.add("+");
        ops.add("-");
        ops.add("*");
        ops.add("/");
        String[] split = expression.split("");
        System.out.println("============中缀表达式==============");
        for (String s : split) {
            System.out.print(s);
        }
        System.out.println();

        //将中缀表达式转换为后缀表达式
        String[] splitSuffix = new String[split.length];
        int indexSuffix = -1;
        MyStack stack = new MyStack(split.length);

        for (String s : split) {
            if (!ops.contains(s) && !s.equals("(") && !s.equals(")")) {
                //如果是数字，直接输出
                //System.out.print(s);
                splitSuffix[++indexSuffix] = s;
            } else if (ops.contains(s)) {
                //如果是+、-、*、/ 判断是否要入栈
                if (stack.isGreaterThanStack(s) || stack.isContainsLeftBrackets()) {
                    stack.push(s);
                }else{

                    String pop = stack.pop();
                    splitSuffix[++indexSuffix] = pop;
                    while (!pop.equals("*")){
                        pop = stack.pop();
                        splitSuffix[++indexSuffix] = pop;
                    }
                    stack.push(s);

                }
            } else if (s.equals("(")) {
                //所有左括号都要入栈
                stack.push(s);
            } else if (s.equals(")")) {
                //不断出栈，直到碰到左括号
                while (true) {
                    String pop = stack.pop();
                    if (pop.equals("(")) {
                        break;
                    }
                    //System.out.print(pop);
                    splitSuffix[++indexSuffix] = pop;
                }
            }
        }
        while (!stack.isEmpty()) {
            String s = stack.pop();
            //System.out.print(s);
            splitSuffix[++indexSuffix] = s;
        }

        System.out.println("============后缀表达式==============");
        for (int i = 0; i <= indexSuffix; i++) {
            System.out.print(splitSuffix[i]);
        }
        //利用栈计算后缀表达式
        for (int i = 0; i <= indexSuffix; i++) {
            String s = splitSuffix[i];
            if (!ops.contains(s)) {
                stack.push(s);
            } else {
                //如果是运算符，连续出栈两次，进行运算，再将运算结果放入栈
                Integer result = 0;
                Integer num1 = Integer.valueOf(stack.pop());
                Integer num2 = Integer.valueOf(stack.pop());
                result = op2(num1, num2, s);
                if (stack.isEmpty()) {
                    System.out.println("运算结果=" + result);
                    break;
                }
                stack.push(result.toString());
            }
        }
    }

    public static int op2(int num1, int num2, String op) {
        switch (op) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            case "/":
                return num1 / num2;
            default:
                return 0;
        }
    }
}

class MyStack {
    private int top = -1;
    private String[] arr;

    public MyStack(int maxLength) {
        this.arr = new String[maxLength];
    }

    public boolean isEmpty() {
        return this.top == -1;
    }

    public boolean isFull() {
        return this.top == arr.length - 1;
    }

    public void push(String element) {
        if (this.isFull()) {
            throw new RuntimeException("数组已满");
        }
        top++;
        this.arr[top] = element;
    }

    public String pop() {
        if (this.isEmpty()) {
            throw new RuntimeException("数组为空");
        }
        return this.arr[top--];
    }

    public boolean isGreaterThanStack(String op) {
        if (this.isEmpty()) {
            return true;
        }
        boolean flag = true;
        if (op == "+" || op == "-") {
            for (int i = 0; i <= this.top; i++) {
                if (this.arr[i].equals("+") || this.arr[i].equals("-") || this.arr[i].equals("*") || this.arr[i].equals("/")) {
                    flag = false;
                    break;
                }
            }
        } else {
            for (int i = 0; i <= this.top; i++) {
                if (this.arr[i].equals("*") || this.arr[i].equals("/")) {
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }

    public boolean isContainsLeftBrackets() {
        if (this.isEmpty()) {
            return true;
        }
        boolean flag = false;
        for (int i = 0; i <= this.top; i++) {
            if (this.arr[i].equals("(")) {
                flag = true;
            }
        }
        return flag;
    }
}
